package tree

import "strconv"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func preOrderTraversal(root *TreeNode) []int {
	var result []int
	var stack []*TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			if len(result) == 0 || root.Val != result[len(result)-1] {
				result = append(result, root.Val)
			}
			stack = append(stack, root)
			root = root.Left
		}

		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		root = root.Right
		if root != nil {
			if len(result) == 0 || root.Val != result[len(result)-1] {
				result = append(result, root.Val)
			}
		}
	}
	return result
}

func inOrderTraversal(root *TreeNode) []int {
	var result []int
	var stack []*TreeNode

	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, root.Val)
		root = root.Right
	}
	return result
}

func postOrderTraversal(root *TreeNode) []int {
	var result []int
	var stack []*TreeNode
	var lastVisit *TreeNode

	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		node := stack[len(stack)-1]
		if node.Right == nil || node.Right == lastVisit {
			stack = stack[:len(stack)-1]
			result = append(result, node.Val)
			lastVisit = node
		} else {
			root = node.Right
		}
	}
	return result
}

// 前序遍历
func preOrderTraversalRecursive(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	result := []int{root.Val}
	result = append(result, preOrderTraversalRecursive(root.Left)...)
	result = append(result, preOrderTraversalRecursive(root.Right)...)
	return result
}

// 中序遍历
func inOrderTraversalRecursive(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	result := inOrderTraversalRecursive(root.Left)
	result = append(result, root.Val)
	result = append(result, inOrderTraversalRecursive(root.Right)...)
	return result
}

// 后序遍历
func postOrderTraversalRecursive(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	result := postOrderTraversalRecursive(root.Left)
	result = append(result, postOrderTraversalRecursive(root.Right)...)
	result = append(result, root.Val)
	return result
}

// heightOfTree 二叉树的高度
func heightOfTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := heightOfTree(root.Left)
	rightHeight := heightOfTree(root.Right)
	if leftHeight > rightHeight {
		return leftHeight + 1
	} else {
		return rightHeight + 1
	}
}

// minHeightOfTree 二叉树的最小高度
func minHeightOfTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := minHeightOfTree(root.Left)
	rightHeight := minHeightOfTree(root.Right)
	if root.Left == nil && root.Right != nil {
		return rightHeight + 1
	}
	if root.Left != nil && root.Right == nil {
		return leftHeight + 1
	}
	if leftHeight == 0 || rightHeight == 0 {
		return leftHeight + rightHeight + 1
	}
	if leftHeight < rightHeight {
		return leftHeight + 1
	} else {
		return rightHeight + 1
	}
}

// levelTraval 层序遍历
func levelTraval(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	var order func(node *TreeNode, level int)
	order = func(node *TreeNode, level int) {
		if node == nil {
			return
		}
		if len(res) == level {
			res = append(res, []int{})
		}
		res[level] = append(res[level], node.Val)
		order(node.Left, level+1)
		order(node.Right, level+1)
	}
	order(root, 0)
	return res
}

// 反转二叉树
// invertTree 递归
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
	return root
}

// 二叉树的所有路径 回溯
// binaryTreePaths 递归
func binaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return []string{}
	}
	if root.Left == nil && root.Right == nil {
		return []string{strconv.Itoa(root.Val)}
	}
	leftPaths := binaryTreePaths(root.Left)
	rightPaths := binaryTreePaths(root.Right)
	paths := []string{}
	for _, path := range leftPaths {
		paths = append(paths, strconv.Itoa(root.Val)+"->"+path)
	}
	for _, path := range rightPaths {
		paths = append(paths, strconv.Itoa(root.Val)+"->"+path)
	}
	return paths
}

// 二叉树路径之和中是否存在目标值
// hasPathSum 递归
func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return sum == root.Val
	}
	return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}

// 是否是平衡二叉树
// isBalanced 递归
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if abs(heightOfTree(root.Left)-heightOfTree(root.Right)) > 1 {
		return false
	}
	return isBalanced(root.Left) && isBalanced(root.Right)
}

// abs 绝对值
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

// 左叶子之和
// sumOfLeftLeaves 递归
func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if isLeaf(root.Left) {
		return root.Left.Val + sumOfLeftLeaves(root.Right)
	}
	return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

// isLeaf 是否是叶子节点
func isLeaf(node *TreeNode) bool {
	if node == nil {
		return false
	}
	return node.Left == nil && node.Right == nil
}

// 获取最深左叶子节点
// deepestLeftLeaf 递归
func deepestLeftLeaf(root *TreeNode, level int) (int, int) {
	if root == nil {
		return 0, 0
	}
	var leftVal, rightVal int
	var leftLevel, rightLevel int
	if isLeaf(root.Left) {
		leftVal, leftLevel = root.Left.Val, level
	} else {
		leftVal, leftLevel = deepestLeftLeaf(root.Left, level+1)
	}
	if isLeaf(root.Right) {
		rightVal, rightLevel = 0, 0
	} else {
		rightVal, rightLevel = deepestLeftLeaf(root.Right, level+1)
	}
	if leftLevel > rightLevel {
		return leftVal, leftLevel
	}
	return rightVal, rightLevel
}

// 根据中序和后序遍历构造二叉树
// buildTree 递归
func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: postorder[len(postorder)-1]}
	index := 0
	for i, v := range inorder {
		if v == root.Val {
			index = i
			break
		}
	}
	root.Left = buildTree(inorder[:index], postorder[:index])
	root.Right = buildTree(inorder[index+1:], postorder[index:len(postorder)-1])
	return root
}

// 最大二叉树
// constructMaximumBinaryTree 递归
func constructMaximumBinaryTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	maxIndex := 0
	for i, v := range nums {
		if v > nums[maxIndex] {
			maxIndex = i
		}
	}
	root := &TreeNode{Val: nums[maxIndex]}
	root.Left = constructMaximumBinaryTree(nums[:maxIndex])
	root.Right = constructMaximumBinaryTree(nums[maxIndex+1:])
	return root
}

// 合并二叉树
// mergeTrees 递归
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	}
	if t2 == nil {
		return t1
	}
	root := &TreeNode{Val: t1.Val + t2.Val}
	root.Left = mergeTrees(t1.Left, t2.Left)
	root.Right = mergeTrees(t1.Right, t2.Right)
	return root
}

// 二叉搜索树搜索指定值
// searchBST 递归
func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == val {
		return root
	}
	if root.Val > val {
		return searchBST(root.Left, val)
	}
	return searchBST(root.Right, val)
}

// 二叉搜索树是否为有效的
// isValidBST 递归
func isValidBST(root *TreeNode) bool {
	return isValidBSTHelper(root, nil, nil)
}

// isValidBSTHelper 递归
func isValidBSTHelper(root *TreeNode, min *int, max *int) bool {
	if root == nil {
		return true
	}
	if min != nil && root.Val <= *min {
		return false
	}
	if max != nil && root.Val >= *max {
		return false
	}
	return isValidBSTHelper(root.Left, min, &root.Val) && isValidBSTHelper(root.Right, &root.Val, max)
}

// 二叉搜索树中序遍历后求数组两元素的最小绝对差
// getMinimumDifference 递归
func getMinimumDifference(root *TreeNode) int {
	res := make([]int, 0)
	inOrderTraversalHelper(root, &res)
	min := res[1] - res[0]
	for i := 1; i < len(res)-1; i++ {
		if res[i+1]-res[i] < min {
			min = res[i+1] - res[i]
		}
	}
	return min
}

// inOrderTraversalHelper 递归
func inOrderTraversalHelper(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	inOrderTraversalHelper(root.Left, res)
	*res = append(*res, root.Val)
	inOrderTraversalHelper(root.Right, res)
}

// 搜索二叉树后序遍历
// postOrderTraversalHelper 递归
func postOrderTraversalHelper(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	postOrderTraversalHelper(root.Left, res)
	postOrderTraversalHelper(root.Right, res)
	*res = append(*res, root.Val)
}

// 搜索二叉树前序遍历
// preOrderTraversalHelper 递归
func preOrderTraversalHelper(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	*res = append(*res, root.Val)
	preOrderTraversalHelper(root.Left, res)
	preOrderTraversalHelper(root.Right, res)
}

// 二叉搜索树的众数
// findMode 递归
func findMode(root *TreeNode) []int {
	res := make([]int, 0)
	inOrderTraversalHelper(root, &res)
	max := 0
	count := 1
	result := make([]int, 0)
	for i := 1; i < len(res); i++ {
		if res[i] == res[i-1] {
			count++
		} else {
			count = 1
		}
		if count > max {
			max = count
			result = []int{res[i]}
		} else if count == max {
			result = append(result, res[i])
		}
	}
	return result
}

// 二叉树获取任意给定两个值的共同祖先
// lowestCommonAncestor 递归
func lowestCommonAncestor(root *TreeNode, p, q int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p || root.Val == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

// 二叉搜索树的公共祖先
// lowestCommonAncestorBST 递归
func lowestCommonAncestorBST(root *TreeNode, p, q int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val > p && root.Val > q {
		return lowestCommonAncestorBST(root.Left, p, q)
	}
	if root.Val < p && root.Val < q {
		return lowestCommonAncestorBST(root.Right, p, q)
	}
	return root
}

// 插入二叉搜索树
// insertIntoBST 递归
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}
	if root.Val > val {
		root.Left = insertIntoBST(root.Left, val)
	} else {
		root.Right = insertIntoBST(root.Right, val)
	}
	return root
}

// 删除二叉搜索树中的节点
// deleteNode 递归
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == key {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		min := getMin(root.Right)
		root.Val = min.Val
		root.Right = deleteNode(root.Right, min.Val)
	} else if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	} else {
		root.Right = deleteNode(root.Right, key)
	}
	return root
}

// getMin 获取最小值
func getMin(root *TreeNode) *TreeNode {
	for root.Left != nil {
		root = root.Left
	}
	return root
}

// 修剪二叉搜索树
// trimBST 递归
func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val < low {
		return trimBST(root.Right, low, high)
	}
	if root.Val > high {
		return trimBST(root.Left, low, high)
	}
	root.Left = trimBST(root.Left, low, high)
	root.Right = trimBST(root.Right, low, high)
	return root
}

// 将有序数组转换为二叉搜索树
// sortedArrayToBST 递归
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	mid := len(nums) / 2
	root := &TreeNode{Val: nums[mid]}
	root.Left = sortedArrayToBST(nums[:mid])
	root.Right = sortedArrayToBST(nums[mid+1:])
	return root
}

// 累加树,大于等于当前节点的所有节点之和
// convertBST 递归
func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	var convert func(node *TreeNode)
	convert = func(node *TreeNode) {
		if node == nil {
			return
		}
		convert(node.Right)
		sum += node.Val
		node.Val = sum
		convert(node.Left)
	}
	convert(root)
	return root
}
